/**
 * @file main.cpp
 * @author 张奕欣 (3190105655@zju.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-12-14
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include "graph.h"
#include <iostream>
#include <string>
#include <vector>
#include <list>
#define INF 1e9
using namespace std;


template <typename VT>
int index(graphVertex<VT> v,vector<graphVertex<VT>> V)
{
    for (int i = 0; i < V.size(); i++)
        {
            if(v == V[i])
                return i;
        }
    return -1;
}

template <typename VT>
void BF(vector<graphVertex<VT>> V,vector<graphEdge<VT>> E)
{
    double dis[V.size()];
    int bak[V.size()];
    
    // 初始化dis[]数组 ak数组
    for (int i = 0; i < V.size(); ++i)
    {
        bak[i] = i;
        dis[i] = INF;
    }
    dis[0] = 0;

    // 然后我们开始v-1次松弛操作
    for (int j = 1;j<V.size();j++)
    {
        int check = 0;
        for (int i = 0; i < E.size(); i++)
        {
            if (dis[index(E[i].Vertex1(),V)] != INF && dis[index(E[i].Vertex2(),V)] > dis[index(E[i].Vertex1(),V)]+E[i].weight())
            {
                dis[index(E[i].Vertex2(),V)] = dis[index(E[i].Vertex1(),V)]+E[i].weight();
                bak[index(E[i].Vertex2(),V)] = index(E[i].Vertex1(),V);
                check = 1;
            }
        }

        if (check==0) break;
    }

    /**
     * @brief 判断是否有负边环
     * 
     */
    int flag = 0;
    for (int i = 0; i < E.size(); i++)
    {
        if (dis[index(E[i].Vertex2(),V)] > dis[index(E[i].Vertex1(),V)]+E[i].weight())
        {
            flag = 1;
        }
    } 

    if (flag == 1)
    {
        cout << "Negative edge ring Exist." << endl;
    }
    else
    {
            for (int i = 0; i<V.size(); i++)
        {
            cout << "from vertex " << V[0].ver() << " to vertex " << V[i].ver() 
                 << " the shortest distance: " << dis[i] << endl;
        }
    
        cout << "For" << V[0].ver() << ", shortest route:";
        for (int i = 1; i<= V.size(); i++)
        {
            cout << V[bak[i]].ver() << "  ";
        }
    }
    
}

int main()
{
    /**
     * @brief 建立一个图
     * 
     */
    vector<graphVertex<string>> V;
    vector<graphEdge<string>> E;

    graphVertex<string> v1{"A"};
    graphVertex<string> v2{"B"};
    graphVertex<string> v3{"C"};
    graphVertex<string> v4{"D"};


    graphEdge<string> edge1{v1, v2, -1};
    graphEdge<string> edge2{v1, v3, 4};
    graphEdge<string> edge3{v2, v3, 3};
    graphEdge<string> edge4{v2, v4, -2};
    graphEdge<string> edge6{v4, v2, 1};
    graphEdge<string> edge7{v4, v3, 5};
    
    V.push_back(v1);
    V.push_back(v2);
    V.push_back(v3);
    V.push_back(v4);
    E.push_back(edge1);
    E.push_back(edge2);
    E.push_back(edge3);
    E.push_back(edge4);
    E.push_back(edge6);
    E.push_back(edge7);

    GraphAdMatrix<string> G{V, E};
    G.listEdges();                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
    G.listVertexes();

    /**
     * @brief 测试Bellman-ford 算法
     * 
     */
    cout << "*****************Test Negative edge ring*****************" << endl;
    BF(V,E);

    vector<graphVertex<string>> V1;
    vector<graphEdge<string>> E1;

    graphEdge<string> edge11{v1, v2, 1};
    graphEdge<string> edge21{v1, v3, 4};
    graphEdge<string> edge31{v2, v3, 3};
    graphEdge<string> edge41{v2, v4, 2};
    graphEdge<string> edge61{v4, v2, 1};
    graphEdge<string> edge71{v4, v3, 5};
    
    V1.push_back(v1);
    V1.push_back(v2);
    V1.push_back(v3);
    V1.push_back(v4);
    E1.push_back(edge11);
    E1.push_back(edge21);
    E1.push_back(edge31);
    E1.push_back(edge41);
    E1.push_back(edge61);
    E1.push_back(edge71);

    cout << "*****************Test Value Count*****************" << endl;
    BF(V1,E1);

}